279. 完全平方数

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/perfect-squares/

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

1
2
3
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

分析

这道题其实是非常简单的动态规划类问题，递推思路很清晰，但是使用python，会出现超时！

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math

class Solution:

    def __init__(self):
        self.dp = None

    def numSquares(self, n: int) -> int:
        self.dp = [0] * (n + 1)
        self.dp[1] = 1
        for i in range(2, n + 1):
            if self.validate_square(i):
                self.dp[i] = 1
            else:
                min_nums = []
                for j in range(1, i):
                    if not self.validate_square(j):
                        continue
                    min_nums.append(self.dp[i - j])
                self.dp[i] = min(min_nums) + 1
        return self.dp[n]

    def validate_square(self, n):
        return math.sqrt(n).is_integer()

优化

本题的关键是完全平方数，因而并不需要对所有数进行判断是否是完全平方数，只需要从1开始递增，找到对应的1*1，2*2等等的完全平方数即可，这样裁剪了很多不必要的分支。

按照这种思路，本文的解法可以是：

1
2
3
4
5
6
7
8
9
10
11
class Solution:

    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = i
            j = 1
            while i - j * j >= 0:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

但是这种方法使用python3仍然会超时，我们用Java重写了一遍，即可通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i < n+1; i++) {
            // 这是最差的一种方式，就是全都是1组成的
            dp[i] = i;
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
}